Родился в семье техника путей сообщения, детство провел на Великом Сибирском железнодорожном пути, в служебном вагоне отца. Окончил 4 класса гимназии в Омске. Начал писать стихи гимназистом. Первая публикация в 1921 («Мы — футуристы невольные...» — в омском журнале «Искусство»). Печатался в журнале «Сибирские огни», «Сибирь»; в 1927 по рекомендации Н.Тихонова — в «Звезде» («Корреспондент»). Был сельским книгоношей, участвовал в геолого-геодезических экспедициях.
В конце 1920-х — начале 1930-х корреспондентом «Сибирских огней», «Сибири», «Наших достижений» много ездил по Сибири, Семиречью, Туркестану.
«Опасный» интерес Мартынова к прошлому Сибири послужил в 1930-е основанием для ссылки Мартынова (и его друга поэта С.Маркова) на Север, в Вологду (образ «прохожего» в стих. «Замечали — / По городу ходит прохожий?..» (1935, 1945) — автобиографический).
По возвращении в Омск Мартынов пишет поэмы (первые поэмы: «Старый Омск», «Адмиральский час», обе — 1924): «Правдивая история об Увенькае, воспитаннике азиатской школы толмачей в городе Омске» (1935–36), «Рассказ о русском инженере» (1936), «Тобольский летописец» (1937), «Домотканая Венера» (1939), «Поэзия как волшебство» (1939) и др. В поэмах-повестях фабульная выдумка при исторической подлинности рассказа, глубокое знание фольклорно-этнографического, историко-бытового материала, многоголосье, масштабность историко-философского фона. Сибирь в эпосе Мартынова — страна цивилизации, творимой людьми разных сословий, возникшей на перекрестке культур многих народов; Сибирь в поэмах — земля, рождающая и принимающая под свое покровительство души сильные, яркие и свободные. Оригинальная стихотворная манера: классический размер передан длинной, прозаизированной строкой.
Первая книга Мартынова — «Стихи и поэмы» (1939) — вышла в Омске.
В 1940 в Москве и Омске появились 2 сборника под заглавием «Поэмы». В сборнике «Лукоморье» и «Эрцинский лес» (оба — 1945) находит завершение сказочно-фантастическая тема Лукоморья, характерная для лирики Мартынова 1930-х.
Обвиненный послевоенной критикой в аполитичности и вневременности своей поэзии, певец Лукоморья почти на десятилетие был лишен возможности печататься. Широкая известность Мартынова началась с выходом сборника «Стихи» (1955), созвучного поре общественного обновления, раскрепощения человека, освобождения его от страхов: «...На деревьях рождаются листья, / Из щетины рождаются кисти, / Холст растрескивается с хрустом, / И смывается всякая плесень... / Дело пахнет искусством. / Человечеству хочется песен» («Что-то новое в мире...», 1948, 1954); определяют основную тональность поэзии Мартынова книги стихов «Градус тепла», «Из смиренья не пишутся стихотворенья...», «След», «Голоса» и др.
В сборниках «Новая книга» (1962), «Первородство» (1965), «Голос природы» (1966), «Людские имена» (1969), «Гиперболы» (1972) — явление поэта-лирика, утверждающего строить — в стихах — «свою державу», где он «заново все создает». Мартынов — летописец духовных сдвигов в сознании людей XX столетия; лирика — дневник состояний, в которых пребывало и еще пребудет человечество (стихи Мартынова дальнозорки). Эмоциональная реакция поэта на происходящее в мире рождается в лирике Мартынова как прямое следствие познания этого мира (читатель стихов приобщается к самому процессу познания — с точки зрения археолога, астронома, математика, биофизика и др.). В лирике Мартынова сильно выражено возрожденческое начало, мысль об ответственности человека за все происходящее, за судьбу Земли («Дедал», «Люди», «Мне кажется, что я воскрес...», «Царь природы» и др.).
В сборнике «Узел бурь» (1979), «Золотой запас» (опубл. 1981) — лирика итогов («...сделав все резкие выпады, / Ты медленно делаешь выводы»), к которым поэт приходит перед бездной вечности. Богатство ассоциативного мышления (звукового, живописного, смыслового) — основа увлекательнейших игр словами, аллитераций, метафор, оригинальных рифм (в т.ч. внутренних и каламбурных), источник словотворчества в поэзии Мартынова.
Мартынов переводил стихи с венгерского, итальянского, чешского, польского и других языков («Поэты разных стран», 1964). Автор книг мемуарной прозы «Воздушные фрегаты» (1974), «Черты сходства» (опубл. 1982).