Before settling on the 2018 Starship design, SpaceX successively presented a number of reusable super-heavy lift vehicle proposals. These preliminary spacecraft designs were known under various names (Mars Colonial Transporter, Interplanetary Transport System, BFR).

In November 2005, before SpaceX had launched its first rocket, the Falcon 1, CEO Elon Musk first mentioned a high-capacity rocket concept able to launch 100 t (220,000 lb) to low Earth orbit, dubbed the BFR. Later in 2012, Elon Musk first publicly announced plans to develop a rocket surpassing the capabilities of the existing Falcon 9. SpaceX called it the Mars Colonial Transporter, as the rocket was to transport humans to Mars and back. In 2016, the name was changed to Interplanetary Transport System, as the rocket was planned to travel beyond Mars as well. The design called for a carbon fiber structure, a mass in excess of 10,000 t (22,000,000 lb) when fully-fueled, a payload of 300 t (660,000 lb) to low Earth orbit while being fully reusable. By 2017, the concept was temporarily re-dubbed the BFR.

In December 2018, the structural material was changed from carbon composites to stainless steel, marking the transition from early design concepts of the Starship. Musk cited numerous reasons for the design change; low cost, ease of manufacture, increased strength of stainless steel at cryogenic temperatures, and ability to withstand high temperatures. In 2019, SpaceX began to refer to the entire vehicle as Starship, with the second stage being called Starship and the booster Super Heavy. They also announced that Starship would use reusable heat shield tiles similar to those of the Space Shuttle. The second-stage design had also settled on six Raptor engines by 2019; three optimized for sea-level and three optimized for vacuum. In 2019 SpaceX announced a change to the second stage's design, reducing the number of aft flaps from three to two to reduce weight. In March 2020, SpaceX released a Starship Users Guide, in which they stated the payload of Starship to low Earth orbit (LEO) would be in excess of 100 t (220,000 lb), with a payload to geostationary transfer orbit (GTO) of 21 t (46,000 lb).

In November 2005, before SpaceX launched the Falcon 1, its first rocket, CEO Elon Musk first referenced a long-term and high-capacity rocket concept named BFR. The BFR would be able to launch 100 t (220,000 lb) to LEO and would be equipped with Merlin 2 engines. The Merlin 2 would have been in direct lineage to the Merlin engines used on the Falcon 9, described as a scaled up regeneratively cooled engine comparable to the F-1 engines used on the Saturn V.

In July 2010, after the final launch of Falcon 1 a year prior, SpaceX presented launch vehicle and Mars space tug concepts at a conference. The launch vehicle concepts were called Falcon X (later named Falcon 9), Falcon X Heavy (later named Falcon Heavy), and Falcon XX (later named Starship); the largest of all was the Falcon XX with a 140 t (310,000 lb) capacity to low Earth orbit. To deliver such payload, the rocket would have been as tall as the Saturn V and use six powerful Merlin 2 engines.

In October 2012, the company made the first public articulation of plans to develop a fully reusable rocket system with substantially greater capabilities than SpaceX's existing Falcon 9. Later in 2012, the company first mentioned the Mars Colonial Transporter rocket concept in public. It was going to be able to carry 100 people or 100 t (220,000 lb) of cargo to Mars and would be powered by methane-fueled Raptor engines. Musk referred to this new launch vehicle under the unspecified acronym "MCT", revealed to stand for "Mars Colonial Transporter" in 2013, which would serve the company's Mars system architecture. SpaceX COO Gwynne Shotwell gave a potential payload range between 150–200 tons to low Earth orbit for the planned rocket. For Mars missions, the spacecraft would carry up to 100 tonnes (220,000 lb) of passengers and cargo. According to SpaceX engine development head Tom Mueller, SpaceX could use nine Raptor engines on a single MCT booster or spacecraft. The preliminary design would be at least 10 meters (33 ft) in diameter, and was expected to have up to three cores totaling at least 27 booster engines.

In 2016, the name of the Mars Colonial Transporter system was changed to the Interplanetary Transport System (ITS), due to the vehicle being capable of other destinations. Additionally, Elon Musk provided more details about the space mission architecture, launch vehicle, spacecraft, and Raptor engines. The first test firing of a Raptor engine on a test stand took place in September 2016.

On September 26, 2016, a day before the 67th International Astronautical Congress, a Raptor engine fired for the first time. At the event, Musk announced SpaceX was developing a new rocket using Raptor engines called the Interplanetary Transport System. It would have two stages, a reusable booster and spacecraft. The stages' tanks were to be made from carbon composite, storing liquid methane and liquid oxygen. Despite the rocket's 300 t (660,000 lb) launch capacity to low Earth orbit, it was expected to have a low launch price. The spacecraft featured three variants: crew, cargo, and tanker; the tanker variant is used to transfer propellant to spacecraft in orbit. The concept, especially the technological feats required to make such a system possible and the funds needed, garnered substantial skepticism. Both stages would use autogenous pressurization of the propellant tanks, eliminating the Falcon 9's problematic high-pressure helium pressurization system.