Tháng 6-2004, Nguyễn Khắc Sơn cùng vợ con bỏ trốn khỏi TP Hồ Chí Minh, mang theo 60 tỷ đồng tiền biển thủ công quỹ và 30 tỷ đồng tiền chiếm đoạt của các cá nhân, đơn vị. Văn phòng cảnh sát Interpol Việt Nam đã phát lệnh truy nã quốc tế và thông báo cho Interpol quốc tế những thông tin ban đầu cũng như ảnh, nhân dạng... của đối tượng, để cảnh sát các nước đưa Sơn vào diện truy nã đặc biệt.
Interpol quốc tế cho biết, trong hơn tám tháng lẩn trốn ở nước ngoài, vợ chồng Sơn luôn di chuyển tới các địa điểm khác nhau để tránh lệnh truy nã. Họ đã từng lưu trú ở một số nước thuộc châu Á trước khi đặt chân đến Mỹ và cuối cùng, bị cảnh sát nước này bắt giữ vào cuối tháng 2-2005.
Ngay sau khi bắt được Sơn, Interpol Mỹ đã thông báo cho Interpol Việt Nam và yêu cầu phía Việt Nam cung cấp những thông tin cụ thể hơn về các hành vi vi phạm pháp luật của Sơn ở Việt Nam, để cơ quan bảo vệ pháp luật của hai nước xúc tiến các thủ tục dẫn độ y. Về những yêu cầu nói trên, Tổng cục Cảnh sát cho biết sẽ báo cáo lên Bộ Công an, Viện KSND tối cao và TAND tối cao để xin ý kiến trả lời chính thức cơ quan bảo vệ pháp luật của Mỹ. Do phải làm các thủ tục pháp lý này nên Interpol Việt Nam trước mắt chưa thể ấn định ngay thời gian dẫn độ Nguyễn Khắc Sơn về Việt Nam.
Trong những năm qua, mặc dù phía Việt Nam và Mỹ chưa ký Hiệp định quốc tế về dẫn độ tội phạm hình sự, nhưng Interpol của hai nước đã có mối liên hệ chặt chẽ và hỗ trợ nhau khá hiệu quả. Cụ thể là đã có không ít trường hợp tội phạm quốc tế nguy hiểm (bị Interpol Mỹ ra lệnh truy nã đỏ) khi xâm nhập vào Việt Nam bị bắt giữ, sau đó các cơ quan bảo vệ pháp luật Việt Nam đã tiến hành các thủ tục pháp lý dẫn độ tội phạm về Mỹ để điều tra, xét xử.
Thiếu tướng Trần Văn Thảo - Tổng cục trưởng Tổng cục Cảnh sát (Bộ Công an) cho biết: Phía Việt Nam đánh giá cao sự hợp tác tích cực của tổ chức cảnh sát Interpol quốc tế nói chung và lực lượng cảnh sát Mỹ nói riêng trong việc bắt giữ Nguyễn Khắc Sơn. Đây là lời cảnh báo chung cho các loại tội phạm hình sự ở trong nước, đặc biệt là tội phạm tham nhũng.
Trước khi bỏ trốn, Nguyễn Khắc Sơn đã cố ý làm trái các quy định của Nhà nước về quản lý kinh tế, tài chính để tham ô tài sản. Điển hình là vụ Sơn chỉ đạo lập phiếu chi tiền cho Công ty Giấy Tân Mai 6,5 tỷ đồng nhưng thực tế không trả công ty này mà bỏ túi riêng. Sơn còn chủ mưu hạch toán số tiền vay bột giấy của Công ty Giấy Đồng Nai là 7,2 tỷ đồng, nhưng thực chất không có chuyện vay mượn. Đặc biệt, Sơn tự ý bán tài sản thế chấp tại ngân hàng, không làm thủ tục giải chấp, không thực hiện đúng quy định của ngân hàng về bán tài sản để tham ô tiền công quỹ.