The contract for construction of the Panzerschiff E (Ersatz Hessen) was signed with the Deutsche Werke shipyard in Kiel on January 25, 1934. The ship was laid down on February 14 of the same year, but the construction process was halted on July 5, 1934 and the slipway was cleared. In practice, the elements of the hull that had already been built were removed from the slipway. Important, however, was the fact that the contract for the construction of the ship remained valid and it was to be resumed as soon as the modified design had been approved.
The most important decision concerning the addition of the third gun turret was made on June 27, 1934 and that was the reason to suspend the construction for some time. However, the 28 cm calibre of the main battery was retained. This decision was taken solely to avoid further delays and the design itself allowed for the subsequent re-armament of the battleship. During the design process, it was recommended that the barbettes were chosen in such a way as to allow for the installation of the larger calibre guns (330, 250 or 380 mm). It was estimated that the re-armament procedure would take approximately 12 to 15 months. The alteration of the number of the main battery guns affected the change of the previous classification from Panzerschiff (armoured ship) into Schlachtschiff (battleship). For the second time the ship was officially laid down on July 6, 1935. The hull was launched on December 8, 1936 and the christening ceremony speech was given by Colonel General Freiherr von Fritsch. The ship’s godmother was the widow of the late Julius Maerker – commander of the armoured cruiser Gneisenau. The launching ceremony did not go without a minor incident. Due to defective drag weights, the launched hull could not be completely stopped, so it hit the wall of the opposite Hindenburg Embankment. Luckily for the ship, the quay sustained more damage than the hull. Further fitting out work continued according to schedule and on May 21, 1938 the ship was commissioned into the Kriegsmarine. Captain Erich Förster, former commander of the light cruiser Karlsruhe, became her commanding officer.
During construction of the battleship a standard transverse and longitudinal layout of the hull braces was used. Individual web frames were set at various distances from 0.75 to 1.5 m, based on the area where they were installed, starting in the stern section, going through the midship towards the bow. The hull was divided into 21 integral watertight compartments, respectively marked with Roman numerals I to XXI. Individual hull compartments had appropriate markings painted on their walls which made it easier for the battleship’s crew to orientate inside the hull. There was a autonomous damage control system in each of the compartments which was integrated with the main as well as the auxiliary damage control stations. The armoured citadel located inside the hull protected all the vital installations such as the engine room, magazines, barbettes, etc. New St 42 and St 52 KM steel was used for the hull construction. High-pressure superheated steam turbines were the designed propulsion system for both Scharnhorst class battleships. The ship received three sets of turbines delivered by Deschimag A. G., Bremen with the power output of 53 350 SHP each. The steam was generated by 12 high-pressure boilers also manufactured by the Deschimag works. During the sea trials the Gneisenau reached the maximum speed of 30.7 knots at the power output of 151 900 HP. Her range at that speed was 2 900 nm, at 19 knots it was 6 200 nm and at 15 knots 8 380 nm. Electrical power was provided by 5 power rooms located in 4 compartments. There were four Diesel generators and eight turbogenerators altogether, generating a total of 4 120 kW at 220 V DC.