Die Besiedelung der Gemarkung Neidenbach geht wohl bis in das römisch-fränkische Zeitalter zurück. Flurnamen und einige archäologische Funde deuten auf eine römische und fränkische Siedlungen um Neidenbach hin. Die Römerstraße Trier-Köln verlief über die Höhen zwischen Neidenbach und dem 2,5 km entfernten Balesfeld. Dort befindet sich ein Grenzstein, der auch auf topologischen Karten erkennbar ist. Dieser trägt die Inschrift FINIS PAGI CARVCVM und weist damit auf eine Siedlung von keltischen Caruces hin.

1177 wurde Neidenbach erstmalig als Nidenbuch in einer Urkunde des Papstes Alexander III erwähnt. Die Urkunde hielt eine Schenkung von Graf Fulco de Malberc fest. Dieser schenkte dem Kloster Himmerod ein Allodium (Erbgut und Gutshof) mit allem Zubehör. Bis zum Ende des 18. Jahrhunderts gehörte Neidenbach teils zu Kurtrier (Amt Kyllburg) und zum Herzogtum Luxemburg (Herrschaft Malberg). Die Grundherrschaft stand dem Herrn von Malberg, Baron von Veyder, und dem Zisterzienserinnen-Kloster Sankt Thomas bei Kyllburg in gleichen Teilen zu. Die beiden Herren setzten ein gemeinschaftliches Gericht ein, von dem die luxemburgischen Untertanen nach Luxemburg, die trierischen nach Trier appellierten. 1531 wurden neun trierische und fünf luxemburgische Feuerstätten (Behausungen) gezählt. 1777 waren es acht trischische und zehn luxemburgische Feuerstätten. Auch in der sogenannten Franzosenzeit war der Ort geteilt. Der zuvor luxemburgische Teil gehörte von 1795 bis 1814 zum Wälderdepartement und der zuvor trierische Teil gehörte von 1798 bis 1814 zum Saardepartement. Nach dem Wiener Kongress (1815) kam Neidenbach zum Königreich Preußen. Nun gehörte Neidenbach ungeteilt zur Bürgermeisterei Malberg und dem 1816 neu gebildeten Kreis Bitburg im Regierungsbezirk Trier, der von 1822 an zur Rheinprovinz gehörte.