Bỏ Sở theo Hán

Năm 209 TCN, Trần Thắng khởi nghĩa chống nhà Tần, Hàn Tín đã ra bờ sông Vị Thủy cầm kiếm xin tham gia nghĩa quân. Ông đã được Hạng Lương là thế tộc nước Sở cho gia nhập nghĩa quân. Tuy nhiên, Hạng Lương và cháu là Hạng Vũ xem thường Hàn Tín thân phận thấp hèn, chỉ cho làm quân cầm kích đứng hầu. Nhiều lần ông bày mưu cho Hạng Vũ, nhưng Hạng Vũ không dùng. Nhà Tần sụp đổ, Hạng Vũ đứng đầu chư hầu, phân phong cho các tướng và vua chư hầu. Lưu Bang bị Hạng Vũ tranh công vào Quan Trung, đẩy vào đất Thục xa xôi hiểm trở, phong làm Hán Vương. Khi Hán Vương lên đường vào đất Thục, Hàn Tín bất mãn vì vẫn không được trọng dụng, bèn bỏ Sở theo về Hán dưới sự tiến cử của Trương Lương. Nhưng ông cũng không được Hán vương coi trọng, bản thân không có tiếng tăm gì, chỉ được làm chức liên ngao, tức là quan coi kho. Hàn Tín đi đến đất Thục, nhưng không muốn đưa thư tiến cử của mình cho Đằng vương Hạ Hầu Anh (lúc này chịu trách nhiệm về việc chiêu hiền đãi sĩ). Ông đã tự mình tiến cử với Hạ Hầu Anh . Hạ Hầu Anh bèn cùng nói chuyện, rất hài lòng, sau đó tâu với Lưu Bang. Lưu Bang cho ông làm độ úy, coi về thóc.

Hàn Tín thường nói chuyện với tướng quốc của Lưu Bang là Tiêu Hà. Hàn Tín có nói với Tiêu Hà 1 câu rất nổi tiếng về người làm tướng như sau

Bẩm Thừa Tướng, đạo làm tướng trước nhất phải có,"năm tài" và tránh "mười lỗi". Năm tài là: trí, nhân, tín, dũng, trung. Trí thì biết cẩn thận, nhân thì biết thương người, tín thì không sai hẹn, dũng thì không ai dám phạm, trung thì không ở hai lòng. Còn mười điều lỗi: một là cậy vào cái dũng khinh thân mình, hai là gặp việc gấp thì nóng nảy, thiếu cẩn thận, ba là gặp lợi thì ham, bốn là vì lòng nhân không dám giết người, năm là ỷ lại vào sức mình không biết lo xa, sáu là tin mà không phòng, bảy là không chịu thu thập ý kiến mọi người, tám là việc đáng làm gấp mà do dự, chín là thiên vị, thiếu công bằng, mười là lười biếng, chỉ muốn sai người. Nếu có đủ "năm tài" và tránh được "mười lỗi" ấy, tất là tướng giỏi. Tiêu Hà rất phục tài ông và hứa tiến cử với Hán Vương.

từ Hàm Dương vào Thục xa xôi, hiểm trở, Lưu Bang cùng các tướng di chuyển trong thời gian khá lâu. Khi Hán Vương đến đất Nam Trịnh, trên đường đi, các tướng thấy cõi Thục độc địa bỏ trốn đến mấy chục người. Hàn Tín xem chừng Tiêu Hà và Hạ Hầu Anh đã mấy lần tâu với Lưu Bang nhưng Lưu Bang không dùng mình, nên cũng bỏ trốn. Tiêu Hà nghe tin Hàn Tín bỏ trốn liền thân hành theo tìm, không kịp báo cho Hán vương biết.Lưu Bang coi Tiêu Hà như cánh tay phải, lúc đó đứng ngồi không yên. Mãi hai hôm sau Tiêu Hà mới về, giãi bày hết với Hán vương và ra sức tiến cử Hàn Tín:

Các tướng đều dễ kiếm thôi, còn như Tín là kẻ quốc sĩ, có một không hai. Nhà vua nếu cứ muốn làm vương mãi ở Hán Trung, thì chẳng cần Tín làm gì chứ nếu muốn tranh lấy thiên hạ thì ngoài Tín ra chẳng có thể bàn công việc với ai.

Lưu Bang dù chưa thật tin nhưng vì sự khẩn khoản của Tiêu Hà mà phong cho Hàn Tín làm đại tướng. Khi Hán vương làm trai giới, lập đàn để phong ông, cả ba quân đều kinh ngạc, không nghĩ rằng người như ông lại được lên làm đại tướng.Hàn Tín lên đàn nhận phong xong, bèn phân tích cho Hán vương về những thế mạnh, yếu của Hạng Vũ và phương sách đánh bại Sở. Hán vương bắt đầu nhận ra tài năng của ông. Về sau mới biết Tín là người được Trương Lương tiến cử nên Lưu Bang lại càng xem trọng.