明治維新の後、富国強兵や殖産興業のために、当時主流だった海運と並ぶ陸上での大量輸送機関である鉄道の整備が求められ、1869年（明治2年）11月に鉄道建設が廟議決定されると、各地で鉄道に関する議論や運動が盛んになった。1872年（明治5年）10月に日本の鉄道が開業すると、華族組合による鉄道の経営を考えていた蜂須賀茂韶が工部卿に送った書簡の中で、「東京ヨリ奥州青森ニ至リ或ハ東京ヨリ越後新潟ニ至ル等ノ地ニ鉄路蒸気汽車ヲ設ケ…」[4]として、東京から開港地である新潟へ鉄道を敷く計画を示す。1874年（明治7年）には中山道幹線建設のためにルート調査に当たっていたリチャード・ヴィカルス・ボイル（Richard Vicars Boyles）の部下の建築師ウィリアム・ゴールウェー（William Galway）と助手のクロード・ウィリアム・キンダー（Claude William Kinder）によって三国峠の偵察が行われる。1881年（明治14年）に日本鉄道が設立されると、これに接続する鉄道の事業計画が新潟県刈羽郡横沢村の山口権三郎によって作られた（後の北越鉄道）。
1884年（明治17年）5月に日本鉄道が高崎まで開通すると、1887年（明治20年）5月に新潟県南魚沼郡下一日市村の岡村貢が「上越鉄道創設趣意書」を作成し、それを元に前橋の高橋周楨、東京の岡村良朗らと上越直線鉄道会社設立事務所を開設し、敷設運動を開始（1888年1月に上越鉄道会社と改称）[5]。各地で鉄道大会を開き、同士を募って気運を高めた。鉄道技師の佐分利一嗣によってルートが検討され、実地調査が行われた。1889年（明治22年）3月には第一次私鉄ブームの企業勃興の流れに乗って組織が上越鉄道株式会社と改められ、前橋に本社が、東京と新発田に事務所が置かれた。1890年（明治23年）には鍬形豊三郎らが発起人となって前橋 - 沼田 - 長岡 - 新発田をつなぐ鉄道敷設の免許申請が政府に提出されたが、「願意の趣聞き届け難く候」と一方的に却下されてしまう[5]（鉄道局長の井上勝が私鉄に批判的だったことに加えて明治23年恐慌が発生していたことも背景にある）。そこで岡村らは再度測量を行い、隧道延長や勾配などを改良した計画図面と目論見書を作成し、群馬・新潟両県で2万筆の署名を集め、両県知事の申し添えを得て「上越鉄道会社創設再願書」を作成し1891年（明治24年）8月に再申請、両県知事も上京して陳情を行ったが再び許可は下りなかった[6]。シベリア鉄道建設開始の報を受けて国防上の観点も加えて計画の見直しが図られ、同年11月に「上越鉄道敷設建白書」が提出された。
1892年（明治25年）6月21日に鉄道敷設法が公布されると、第一期予定線として「新潟県下直江津又ハ群馬県下前橋若ハ長野県下豊野ヨリ新潟県下新潟及新発田ニ至ル鉄道」が示され、これが法律によって上越線が認められた起源となる[5]。1893年（明治26年）2月の鉄道会議で、上越線（前橋 - 新潟）、直江津延長線（直江津 - 新潟）、豊野線（豊野 - 新潟）の方針について議論が行われた[7]。ここでは23名の出席者のうち、直江津延長線に賛成の者15名、豊野線に賛成の者8名となり、直江津案に決まった。1894年（明治27年）3月の第3回衆議院議員総選挙に新潟7区から立憲改進党として立候補して当選した岡村は、高津仲次郎や湯浅治郎らと糾合して「予定鉄道線路中私設鉄道会社ニ敷設許可ニ関スル法律」の修正案を提出し、国政の場で上越線の重要性を訴えたが、産業発達の誘導や、貨物運輸に便が多いことが認められつつも、技術的に困難であることや、降雪地帯であること、建設費の高さなどが取り沙汰された結果、8票差で否決された[5]。一方で、帝国陸軍の川上操六（鉄道会議議長）は衛戍地である新発田を通る上越線に着目、同計画を進める意見を主張し、岡村や湯浅らも賛成したが、採決の結果、否決された。同年6月に「鉄道比較線路決定ニ関スル法律」（明治27年法律第7号）が公布され、予定線は直江津線（現在の信越本線）となり、上越線は計画から除外された[5]。
官製による敷設が見込めないという結論に至った岡本らは、民間で鉄道を敷設すべく、1894年（明治27年）に毛越鉄道株式会社を発起、1895年（明治28年）6月に上越鉄道会社に改名し、前橋 - 長岡の鉄道敷設免許を申請するが認められなかった。資金を調達するため、会社を株式会社（上越鉄道株式会社創立事務所）に改め、ルート上最も困難と目されていた県境部分のより詳細な測量を行い、報告書を作成した。こういった運動や陳情が実を結び、1896年（明治29年）7月についに敷設の仮免許が下付された。しかし、日清戦争の勝利によって物価が急騰し、500万円を予定していた資本金が3倍の1,500万円を要する事態となった。毛越鉄道では当初、前橋 - 沼田 - 谷川 - 湯沢 - 六日町 - 小千谷 - 長岡を経て新津 - 新発田という計画だったが、その後、長岡以北は計画の重複する北越鉄道に譲っており、経済界ではこれを有利な路線ではないと見て、融資に消極的な姿勢が広がり、資金の調達は難航した[8]。1900年（明治33年）4月、待望の本免許が下付されるものの、経営方針を巡って会社内部で対立が起き、1901年（明治34年）4月には会社が解散し、免許も返納の憂き目を見る。
上越鉄道株式会社の解散総会に出席した土樽村村長の南雲喜之七は、個人の連帯による敷設運動の難しさを目の当たりにし、大きな力を動かすことの必要性を実感していた（南雲は岡村と協力し、運動の初期から参加していた）。1900年に結党された立憲政友会は逓信大臣の原敬を筆頭に交通政策を主要な路線として掲げて党勢の拡大を図っており、南雲は村長の任期を勤め上げた後で政友会に入会すると、1906年の鉄道国有法を経て、1907年（明治40年）に上京し、地方経済の発展のためにも上越線の敷設が急務であることを各所に訴えた[8]。当時、衆議院の請願委員長で南雲と同郷の竹越與三郎（新潟県の郡部から選出）の口添えもあって、1909年（明治42年）3月23日には政友会の日向輝武他1名を代表人として「上越鐵道敷設に關する建議案」が帝国議会に提出された[9]。1910年（明治43年）3月19日には同じく政友会の根岸?太郎他3名により同名の建議案が提出されている[10]。どちらの建議案においても、日露戦争を踏まえて軍事上においての上越線の必要性を訴える内容が大きくなっている。1913年（大正2年）の帝国議会における加藤勝彌による建議の提出や、1916年（大正5年）にも須藤嘉吉らによる建議の提出、他にも地元住民からの陳情や請願書が採択され、期成同盟会による要望が盛んに行われるものの、いずれも具体化には至らなかった。一方、第一次世界大戦やロシア革命によって大陸からの圧力が高まる中で国内では戦争特需が起きて経済が活発になるものの、アプト式の碓氷峠を経由する必要のある信越本線では輸送力の向上に限界があり、同じく日本海側と太平洋側を結んでいた岩越線で1917年（大正6年）3月に松野トンネル崩落事故が起きると、貨客の流動はますますひっ迫した。これらの事態を受けて政府は測量隊を上越国境に派遣し、建設計画の本格的な検討を始めた。やがて1918年（大正7年）2月に上越線「群馬県下高崎ヨリ新潟県下長岡ニ至ル鉄道」を含む改正鉄道敷設法が可決され[11]（大正7年法律第12号）、ここに岡村らの訴えの始まりより30余年を経て上越線の建設が決定した。また、法改正を受けて直ちに直轄事業で工事が着工された。
1920年（大正9年）には新潟県側の上越北線（じょうえつほくせん）の第一期工事として宮内駅（長岡駅） - 東小千谷駅（現・小千谷駅）間、1921年（大正10年）には群馬県側の上越南線（じょうえつなんせん）新前橋駅 - 渋川駅間が開業した。両線は順次延長され、1925年（大正14年）には北線が越後湯沢駅まで、1928年（昭和3年）に南線が水上駅まで開業している。
このほか、高崎駅 - 新前橋駅間は1884年（明治17年）に日本鉄道が高崎駅 - 前橋駅間を開業させた際に建設したもので、国有化後は両毛線の所属となっていたが、上越線全通後に上越線にも属する重複区間となり、1957年（昭和32年）に上越線単独の区間とされた。