В конце концов, в 1935 году проект авианосца в целом удалось завершить, вернее довести до такой стадии, при которой стал возможен заказ корабля на судостроительной верфи и его строительство по меньшей мере до спуска на воду. Были закончены строительные чертежи, размещены заказы на различное оборудование, но при этом разработка многих систем и устройств все еще продолжалась. Особенно это касалось летно-технического оборудования, и здесь, забегая вперед необходимо отметить, что некоторые устройства не удалось завершить даже к середине войны, когда достройка головного авианосца тормозилось именно их отсутствием и в конце концов была определена нецелесообразной.

Результатом принятых мер стало то, что уже 18 ноября 1935 года, всего через несколько месяцев после заключения англо-немецкого военно-морского соглашения, когда Германия получила право строить авианосцы, был подписан договор с фирмой "Deutsche Werke Kiel A.G." в Киле на строительство головного авианосца "А". Закладка корабля состоялась только через год, 28 декабря 1936 года - пришлось ожидать освобождения стапеля, на котором строился линейный корабль "Gneisenau", В период постройки авианосец обозначался как "заказ 252", а во время спуска на воду 8 декабря 1938 года получил имя "Graf Zeppelin". Церемония спуска на воду первого германского авианосца была обставлена весьма торжественно. Присутствовало все партийные и военные руководители Рейха - лично сам Гитлер, Командующий Kriegsmarine генерал-адмирал Редер (Generaladmiral Raeder), Командующий Luftwaffe генерал-фельдмаршал Геринг (General-feldmarschall Goring), Верховный Главнокомандующий генерал-полковник Браухич (Generaloberst Brauchitsch) и Командующий Wehrmacht'oм генерал-полковник Кейтель (Generaloberst Keitel). Крестной матерью авианосца стала дочь графа Цеппелина - графиня Хелла фон Бранденштейн-Цеппелин (Grafin Hella von Brandenstein-Zeppelin).

Второй авианосец, "В", был заказан верфи "Friedrich Krupp Germania Werft" также в Киле (Kiel-Gaarden). Он получил официальный заводской номер "заказ 555", но работы по его строительству были начаты позже и к тому же намеренно тормозились, так как немецкие инженеры хотели максимально использовать в нем весь опыт, накопленный при строительстве головного авианосца. В соответствии с строительным графиком спуск на воду предполагался на 1 июля 1940 года. Довоенные источники печати не раз сообщали о спуске на воду этого авианосца, называлось даже присвоенное ему имя - "Peter Strasser". Однако только после войны стало известно, что работы на нем были остановлены задолго до спусковой готовности, и сейчас с полной уверенностью можно утверждать, что вопрос о наименовании корабля на обсуждение не ставился.

В целом к 1936 году, когда проект авианосца был практически полностью завершен, а первые сведения о нем появились в официальной немецкой печати, конструкция первого немецкого авианосца мало отличалась от иностранных кораблей этого класса. Авианосец получил открытую полетную палубу со свесами в оконечностях и смещенной к правому борту надстройкой, а также двухъярусный ангар под полетной палубой. Первоначальный вариант проекта, по примеру британского "Courageous", предусматривал наличие в носовой части стартовой платформы для самолетов-истребителей, которую разместили ниже уровня основной полетной палубы. Для старта самолеты на нее должны были выводиться через специальные ворота в носовой переборке ангара, прямо под катапультами.

Корпус предполагался почти полностью сварным (за исключением узлов и связей с участием броневой стали), причем полетная палуба и отдельные детали ангаров были включены в набор корпуса, конструктивно обеспечивая ему дополнительную прочность - это не стало новшеством и уже применялось англичанами на своих кораблях, например "Ark Royal". Внутреннее пространство ниже броневой палубы делилось на 20 водонепроницаемых отсеков. Обводы корпуса были спроектированы так, чтобы корпус без какого-либо балласта обеспечивал на левом борту компенсацию веса островной надстройки. Эта идея также была воплощена несколько раньше на "Ark Royal", однако сами англичане в открытой печати признавали, что в будущем, когда возникнет необходимость модернизации корабля и размещения на авианосце дополнительных верхних весов, подобное решение может вызвать некоторые трудности. Тем не менее британские конструкторы, имевшие достаточный опыт проектирования авианосцев, могли предусмотреть эти проблемы заранее. Немецким инженерам пришлось столкнуться с этими трудностями в гораздо более сложных условиях - проект "Grafa Zeppelin'a" к моменту утверждения рабочих чертежей и заключения строительного контракта был очень долек от полной готовности. Как в последующем оказалось, весовые нагрузки даже уже имевшегося оборудования были рассчитаны неправильно, не говоря уже о нагрузках еще не спроектированных устройств и систем. В полной меры эти проблемы проявились во время будущих изменений и дополнений проекта и особенно в период модернизации авианосца,

Проект предусматривал для авианосца броневую защиту аналогичную крейсерам. Броневой пояс толщиной 100 мм в средней части прикрывал машинно-котельные отделения, а в оконечностях утончался до 80 мм. Броневая палуба толщиной в горизонтальной части 40 мм почти на всем протяжении корабля имела 60-мм скосы к нижней кромке поясной брони. Легкое бронирование из 20-мм плит имела также полетная палуба. Тонкой броней прикрывались также казематы противокорабельных орудий.

На авианосце предусматривалась приемлемая по немецким стандартам довоенного времени система подводной защиты, однако свойственная немецкому флоту того времени недооценка возросшей мощи торпедного оружия делала эти стандарты несовершенными уже для середины 30-х годов. По первоначальному проекту конструктивная подводная защита включала двойное дно и специальные защитные бортовые отсеки, из которых внутренние заполнялись топливом, а внешние оставались пустыми. Главным компонентом являлась 20-мм противоторпедная переборка, толщина которой уже в то время признавалась явно недостаточной, также как и общая ширина защиты внутри корпуса. К этому следует добавить, что позже, при модернизации проекта, на "Graf Zeppelin" были пристроены бортовые були. И хотя это было вызвано в большей степени необходимостью улучшения остойчивости корабля, а не желанием улучшить его защиту, тем не менее только это позволило считать защиту авианосца более или менее приемлемой. Об этом будет сказано дальше по тексту.

Главная энергетическая установка авианосца состояла из четырех одинаковых турбозубчатых агрегатов общей мощностью 200 тысяч л.с., каждый из которых включал турбины высокого, среднего и низкого давления, а также маршевую и заднего хода. Котельная установка предполагалась из шестнадцати прямоточных котлов La Mont с принудительной циркуляцией и высокими рабочими параметрами пара (450 градусов и 85 ат.). Недостатки прямоточных котлов, широко применявшихся в немецком флоте того времени, уже известны довольно хорошо, поэтому останавливаться на них не имеет смысла. Можно только сказать, что они совершенно не оправдали надежд немецких моряков, оказались малоэффективными, неэкономичными и, что особенно важно, очень и очень ненадежными в эксплуатации, что выражалось высоким уровнем аварийности и сбоев в работе. Расположение отсеков энергетической установки определялось конструкцией корабля - обычного для того времени эшелонирования установки не предполагалось - турбинные отсеки размещались в корму от котельных. Скорость по контракту предполагалась 34 узла, но ожидалась больше по крайней мере на узел.

Большие изменения были произведены в вооружении корабля. В западных странах до конца войны так и не узнали, что первый немецкий авианосец вполне мог получить 203-мм орудия. Морское командование согласилось на уменьшение калибра до 150 мм, но при этом настаивало на увеличении количества стволов. Так как размещение дополнительных орудий требовало серьезной переделки проекта, вопрос об артиллерии долгое время оставался спорным, из-за чего в проекте остались только восемь 150-мм орудий на одноствольных лафетах. Позже проектанты, с целью уменьшения нагрузки и более эффективного использования помещений, предложили разместить те же восемь орудий на спаренных лафетах специального образца, уменьшив таким образом количество установок до четырех. Морское командование не согласилось с таким решением и к тому же воспользовалось новой идеей, настояв на своем прежнем требовании о увеличении числа стволов и добившись размещения на авианосце восьми теперь уже спаренных лафетов с 150-мм орудиями.