Trong vòng 5 năm sau khi đỗ Giải nguyên, Phan Bội Châu bôn ba khắp nước Việt Nam kết giao với các nhà yêu nước như Phan Chu Trinh[4], Huỳnh Thúc Kháng, Trần Quý Cáp, Nguyễn Thượng Hiền, Nguyễn Hàm (tức Tiểu La Nguyễn Thành), Đặng Nguyên Cẩn, Ngô Đức Kế, Đặng Thái Thân, Hồ Sĩ Kiện, Lê Huân, Nguyễn Quyền, Võ Hoành, Lê Đại,...
Tượng Phan Bội Châu tại Bến Ngự, Huế
Năm 1904, ông cùng Nguyễn Hàm và khoảng 20 đồng chí khác thành lập Duy Tân hội ở Quảng Nam để đánh đuổi Pháp, chọn Kỳ Ngoại hầu Cường Để - một người thuộc dòng dõi nhà Nguyễn - làm hội chủ.
Năm 1905, ông cùng Đặng Tử Kính và Tăng Bạt Hổ sang Trung Quốc rồi sang Nhật Bản, để cầu viện Nhật giúp Duy Tân hội đánh đuổi Pháp. Tại Nhật, ông gặp Lương Khải Siêu, một nhà cách mạng người Trung Quốc, và được khuyên là nên dùng thơ văn (nghe lời Phan Bội Châu viết Việt Nam vong quốc sử) để thức tỉnh lòng yêu nước của nhân dân Việt Nam. Lại nghe hai nhân vật quan trọng của Đảng Tiến Bộ đang cầm quyền ở Nhật Bản, là Bá tước Ôi Trọng Tín (Okuma Shigenobu) và Thủ tướng Khuyển Dưỡng Nghị (Inukai Tsuyoshi) khuyên là nên cổ động thanh niên ra nước ngoài học tập để sau này về giúp nước.
Tháng 6 năm 1905, Phan Bội Châu cùng Đặng Tử Kính mang theo một số sách Việt Nam vong quốc sử về nước. Tháng 8 năm 1905 tại Hà Tĩnh, ông và các đồng chí nồng cốt trong Duy Tân hội bàn bạc rồi đưa ra kế hoạch hành động đó là:
Nhanh chóng đưa Kỳ Ngoại hầu Cường Để ra nước ngoài.
Lập các hội nông, hội buôn, hội học để tập hợp quần chúng và để có tài chánh cho hội.
Chọn một số thanh niên thông minh hiếu học, chịu được gian khổ, đưa đi học ở nước ngoài[5].
Phát động phong trào Đông Du
Bài chính: Phong trào Đông Du
Trong ba nhiệm vụ trên, thì nhiệm vụ thứ ba hết sức quan trọng và bí mật, nên Duy Tân hội đã cử Phan Bội Châu và Nguyễn Hàm tự định liệu. Sau đó, phong trào Đông Du được hai ông phát động, được đông đảo người dân ở cả ba kỳ tham gia và ủng hộ, nhất là ở Nam Kỳ.
Tháng 10 năm 1905, Phan Bội Châu trở lại Nhật Bản cùng với ba thanh niên, sau đó lại có thêm 45 người nữa. Năm 1906, Cường Để qua Nhật, được bố trí vào học trường Chấn Võ. Kể từ đó cho đến năm 1908, số học sinh sang Nhật Bản du học lên tới khoảng 200 người, sinh hoạt chung trong một tổ chức có quy củ gọi là Cống hiến hội...
Tháng 3 năm 1908, phong trào "cự sưu khất thuế" (tức phong trào chống sưu thuế Trung Kỳ nổi lên rầm rộ ở Quảng Nam rồi nhanh chóng lan ra các tỉnh khác. Bị thực dân Pháp đưa quân đàn áp, nhiều hội viên trong phong trào Duy Tân và Duy Tân hội bị bắt, trong số đó có Nguyễn Hàm, một yếu nhân của hội[6].
Mất mát này chưa kịp khắc phục, thì hai phái viên của hội là Hoàng Quang Thanh và Đặng Bỉnh Thành lại bị Pháp đón bắt được khi từ Nhật về Nam Kỳ nhận tiền quyên góp cho phong trào Đông Du. Tiếp theo nữa là Pháp và Nhật vừa ký với nhau một hiệp ước (tháng 9 năm 1908), theo đó chính phủ Nhật ra lệnh trục xuất các du học sinh người Việt ra khỏi đất Nhật. Tháng 3 năm 1909, Cường Để và Phan Bội Châu cũng bị trục xuất. Đến đây, phong trào Đông Du mà Phan Bội Châu và các thành viên khác đã dày công xây dựng hoàn toàn tan rã, kết thúc một hoạt động quan trọng của hội.
Lúc này, ở nhiều nơi trong nước, mọi hoạt động quyên góp tài chính và chuẩn bị vũ trang bạo động của Duy Tân hội cũng bị thực dân cho quân đến đàn áp dữ dội. Những người sống sót sau các đợt khủng bố đều phải nằm im, hoặc vượt biên sang Trung Quốc, Xiêm La, Lào để mưu tính kế lâu dài.
Cuối năm 1910, Phan Bội Châu chuyển một đại bộ phận hội viên (trong đó có khoảng 50 thanh niên) ở Quảng Đông về xây dựng căn cứ địa ở Bạn Thầm (Xiêm La). Tại đây, họ cùng nhau cày cấy, học tập và luyện tập võ nghệ để chuẩn bị cho một kế hoạch phục quốc sau này.
Thượng tuần tháng 5 năm Nhâm Tý (tháng 6 năm 1912), trong cuộc “Đại hội nghị” tại từ đường nhà Lưu Vĩnh Phúc ở Quảng Đông (Trung Quốc), có đông đủ đại biểu khắp ba kỳ đã quyết định giải tán Duy Tân hội và thành lập Việt Nam Quang phục Hội, tức thay đổi tôn chỉ từ chủ nghĩa quân chủ sang chủ nghĩa dân chủ để đánh đuổi quân Pháp, khôi phục Việt Nam, thành lập nước Cộng hòa Dân quốc kiến lập Việt Nam [7], đáp ứng tình hình chuyển biến mới trên trường quốc tế.