Проектирование G4M началось в сентябре 1937 г, когда боевой опыт применения бомбардировщиков Мицубиси G3M показал недостаточные оборонительные возможности последнего. Мицубиси было предложено усилить вооружение G3M, хотя даже морскому штабу было ясно, что при столь узком фюзеляже это вряд ли возможно. В результате имперский флот в сентябре 1937 г направил на Мицубиси требования 12-Си на новый средний бомбардировщик под два двигателя мощностью 1000 л.с. В задании определялось более мощное вооружение, чем у G3M2, скорость до 400 км/ ч на высоте 3000 м, максимальная дальность без бомб - 4750 км, с 800-кг торпедой - 3650 км.
Задача для сравнительно небольшого коллектива Киро Хоне была неподъемной, так как они еще отвечали за модернизацию предыдущей модели. В результате было решено отдать приоритет модернизации G3M2. С подготовкой для серии модернизированного "типа 96 модель 22" Киро Хоне и его конструктора смогли сосредоточиться на разработке новой машины. Для установки необходимого вооружения и оборудования бомбоотсека, а также для облегчения обслуживания самолета, Киро Хоне выбрал для фюзеляжа сигарообразную форму, значительно большую по диаметру, чем у предшественника. Вооружение должно было состоять из четырех 7,7-мм пулеметов "тип 92" в носовой шаровой установке, в верхней башне и двух бортовых блистерах, а в хвостовой башне должна была устанавливаться 20-мм пушка "тип 99 модель 1". Учитывая такую ширину фюзеляжа и большой состав вооружения, Киро Хоре сомневался, что с имеющимися двигателями удастся достигнуть требуемых характеристик. К счастью для него, на Мицубиси уже разрабатывался новый 14-цилиндровый двигатель воздушного охлаждения, обещавший минимум 1500 л.с. на взлете. Киро Хоне обратился в штаб флота за разрешением установить новые двигатели на свой самолет. С этими двигателями можно было достичь заданной скорости, но требовалось увеличить запас топлива. Для этого Киро Хоне спроектировал двухлонжеронное крыло, вмещавшее непротектированный интегральный топливный бак, что позволило довести запас топлива до 4900 л. Бомбовая нагрузка предусматривалась из 800-кг торпеды или бомб соответствующего веса в бомбоотсеке. При подвеске бомб в отсек с него снимались створки - они ставились только при пустом бомбоотсеке.
Макет самолета был готов в августе 1938 г, а изготовление опытного образца началось в следующем месяце. Самолет получил 1530-сильные двигатели Мицубиси МК4А "Касей"-11 с трехлопастными винтами. Опытный G4M1 совершил свой первый полет 23 октября 1939 г под управлением Кацузо Сима. Летные испытания прошли успешно, и на втором опытном самолете потребовалось только несколько увеличить вертикальное оперение и оснастить триммеры элеронов балансирами. Первый самолет был также доработан и в январе 1940 г передан флоту. Во время войсковых испытаний самолет достиг скорости 440 км/ч, а дальность полета достигала 5500 км - значительно больше заданных спецификациями 12-Си. Хотя пилоты отзывались об управляемости самолета положительно, и, казалось, его можно запускать в производство, морской штаб тянул еще год, прежде чем вынес свое положительное решение.