Письмова згадка про село (знаходиться в Кишинівському державному архіві) відноситься на 1572 рік, а саме грамота пана Недоби.
За даними на 1859 рік у власницькому селі Недобоуці Хотинського повіту Бессарабської губернії, мешкало 959 осіб (385 чоловічої статі та 574 — жіночої), налічувалось 209 дворових господарств, існувала православна церква.
Станом на 1886 рік у власницькому селі Недобоуці Рукшинської волості мешкало 1432 осіб, налічувалось 304 дворових господарства, існувала православна церква. Перша згадка про село, а саме грамота пана Недоби, знаходиться в Кишинівському державному архіві і датується 1572 роком. Саме цю дату взято за час заснування села Недобоївці. Назва села є незмінною і походить від прізвище Недоба — власника земельних володінь, на яких поселилися перші жителі. Тривалий час це поселення було дуже малим — налічувало до десяти дворів. Навіть 1771 року мало лише 28 хат. Протягом майже 300 років Недобоївці переходили від одного поміщика до іншого. У грамотах за 1629,1630 і 1632 рр. зазначено, що село було власністю поміщика М.Катарджі.
Розташоване на шляху, котрим проходили війська різних країн, село зазнавало спустошень. Чимало лиха завдала йому російсько-турецька війна (1735—1739 рр.), особливо напередодні і під час Ставчанської битви (серпень 1739 рік). Турецька армія під командуванням сераскера Валі-паші стояла біля Недобоївців і завдала йому великих руйнувань, пограбувала населення.
Чужоземний гніт гальмував зростання Недобоївців. Розвиток села дещо прискорився лише після приєднання Хотинського повіту до Росії в 1812 році за Бухарестським мирним договором. Сталися зміни в його економіці, почало збільшуватися населення. За 1817—1883 рр. воно зросло у 8 разів і становило 1666 чоловік.
Подальший розвиток капіталістичних відносин у сільському господарстві сприяв збільшенню кількості господарств, які почали вирощувати технічні культури.
У листопаді 1918 року село окупували війська королівської Румунії.
День визволення від румунського панування (28 червня 1940 року) став великою радістю для селян.
У селі почали працювати клуб, бібліотека, амбулаторія, акушерський пункт, споживча кооперація. 16 вересня 1940 року вперше відкрила свої двері початкова школа з українською мовою навчання. 1940/41 навчального року здобувало освіту 175 учнів, працювало 4 вчителі. 6 липня 1941 року німецько-румунські війська захопили Недобоївці. Недобоївчани брали участь у партизанському загоні, очолюваному П. Ф. Горчаком. 30 березня 1944 року частини 1318 -го стрілецького полку 163-ї стрілецької дивізії визволили село. В перші ж дні 412 уродженців села стали воїнами Червоної Армії. 38 чоловік було нагороджено бойовими орденами й медалями. Смертю хоробрих на фронтах загинуло 163 чоловіка. В центрі села встановлено пам’ятник воїнам — визволителям.
