The combined use of seawater and recycled tire aggregate (RTA) in concrete is potentially a way forward towards sustainable construction. It can help control harvesting of natural aggregates, manage waste tires, mitigate freshwater consumption and desalination impacts. The current paper aims at investigating the material performance and cost effectiveness of concrete mixed with seawater and RTA. The paper consists of two parts. The first part studies the characteristics (fresh and hardened) of concrete mixed with seawater and RTA. Thirteen concrete mixtures, varying in mixing water (seawater/freshwater) as well as fine and coarse aggregates (at 0%, 5%, 10%, and 20% replacement levels), were investigated. An extensive experimental program was conducted to compare the thirteen mixtures in terms of physical properties, workability, strength, water absorption, and chloride permeability. The second part of the paper performs a life cycle cost analysis (LCCA) for a 20-story building over a 100-year analysis period to verify the cost effectiveness of a proposed sustainable concrete that combines seawater, RTA (at 5% replacement level), and glass fiber-reinforced polymer (GFRP) reinforcement. A sensitivity analysis was performed to investigate the effect of the discount rate on the LCCA results.