Tiền thân của Công ty Vận chuyển khí Đông Nam Bộ (Khí Đông Nam) là Trung tâm Vận hành Khí, được thành lập ngày 31/3/1995 và thuộc Công ty Chế biến và Kinh doanh các sản phẩm Khí nay là PV GAS.

Ngày 26/4/1995, dòng khí đầu tiên được đưa vào bờ, đến ngày 1/5/1995 dòng khí thương mại đầu tiên được cung cấp cho Nhà máy điện Bà Rịa hoạt động với lưu lượng 950.000 m3/ngày đêm, góp phần giảm bớt khoản chi ngoại tệ lớn từ ngân sách Nhà nước cho việc nhập khẩu nhiên liệu. Đây là bước ngoặt đánh dấu một kỷ nguyên mới - kỷ nguyên của ngành công nghiệp khí Việt Nam.

Không dừng ở đó, Khí Đông Nam tiếp tục phối hợp tiếp nhận các giàn nén khí nhỏ, giàn nén khí lớn và mở rộng hệ thống đường ống dẫn khí trên bờ để đạt được những mục tiêu mới. Chưa đầy hai năm sau, vào ngày 25/2/1997 công suất đưa khí vào bờ đã được nâng lên 2 triệu m3/ngày đêm, và cuối năm 1997 công suất đạt 3 triệu m3/ngày đêm, đủ năng lực cung cấp khí cho các nhà máy điện Phú Mỹ 2.1 và 2.1 mở rộng.

Để đáp ứng nhu cầu nhiên liệu khí cho sản xuất công nghiệp đang ngày càng phát triển mạnh, Khí Đông Nam tiếp nhận thêm hệ thống thu gom và dẫn khí dài 45 km để đưa thêm 1 triệu m3 khí/ngày đêm từ mỏ Rạng Đông về mỏ Bạch Hổ, nâng công suất của dự án khí đồng hành mỏ Bạch Hổ từ 4,7 triệu m3/ngày đêm lên 5,7 triệu m3/ngày đêm.

Toàn bộ dự án khí Bạch Hổ được vận hành và khai thác có hiệu quả với 3 loại sản phẩm: khí khô 1,5 tỷ m3/năm, khí hóa lỏng (LPG) 350.000 tấn/năm và condensate (xăng nhẹ) 130.000 tấn/năm.

Đến ngày 12/9/2002, Xí nghiệp Vận chuyển khí được thành lập, với 91 cán bộ công nhân viên, nhận nhiệm vụ chính là vận hành, bảo dưỡng hệ thống đường ống dẫn khí từ ngoài giàn vào bờ, các trạm và trung tâm phân phối khí, các công trình và thiết bị phụ trợ có liên quan. Nhận khí ẩm và phân phối khí khô tới các hộ tiêu thụ.

Vượt qua nhiều chặng đường lịch sử, đến ngày 15/8/2007, thực hiện chủ trương chuyển đổi các Tổng công ty nhà nước thành các tập đoàn kinh tế, Công ty Vận chuyển khí Đông Nam Bộ chính thức được thành lập trên cơ sở Xí nghiệp Vận chuyển Khí. Đồng thời tiếp nhận, vận hành hệ thống đường ống dẫn khí Phú Mỹ - Tp.HCM dài hơn 50 km với 2 trạm khí là Nhơn Trạch và Hiệp Phước vươn tới thị trường tỉnh Đồng Nai và Tp.HCM.

Dự án Giàn nén khí mỏ Rồng - Đồi Mồi được đưa vào vận hành ngày 30/11/2010 với mục đích thu gom, tiếp nhận và xử lý khí đồng hành khu vực mỏ Rồng - Đồi Mồi.

Dự án Giàn nén khí mỏ Rồng - Đồi mồi ước thực hiện thu gom khoảng 2,56 tỷ m3 khí. Tuy nhiên, chỉ sau hơn 5 năm đưa vào vận hành, dự án đã thu gom và vận chuyển được hơn 1,6 tỷ m3 khí về bờ, điều đó khẳng định hiệu quả đầu tư của dự án và cũng là thể hiện tinh thần làm việc chủ động, sáng tạo, dám nghĩ, dám làm, phối hợp nhịp nhàng hiệu quả giữa 2 tập thể Xí nghiệp Khí - Vietsovpetro và Khí Đông Nam  - PV GAS.

Đây còn là công trình thu gom khí đầu tiên ngoài biển do PV GAS đầu tư 100%, Vietsovpetro làm dịch vụ thiết kế, xây lắp và vận hành trọn gói. Dự án này đã hoàn thành trong thời hạn ngắn kỷ lục, làm lợi được 22,5 triệu USD do đưa vào vận hành sớm.

Với sự kiện “Gas in” dự án thu gom khí Hàm Rồng - Thái Bình ngày 7/8/2015 đánh dấu cột mốc mới của Khí Đông Nam mở rộng ra miền Bắc. Đây là địa bàn làm việc khó khăn so với các công trình khí mà Khí Đông Nam đang quản lý từ trước tới nay. Tuy nhiên, công ty xác định đây vừa là cơ hội vừa là thách thức đối với công tác quản lý, vận hành công trình khí. Với tinh thần nỗ lực vượt qua thách thức, đến nay dự án đã đi vào vận hành an toàn và ổn định.

Ngày 5/12/2015, dòng khí đồng hành đầu tiên từ mỏ Đại Hùng đã đưa và hệ thống đường ống Nam Côn Sơn 2 giai đoạn 1 để đưa về bờ, đánh dấu một cột mốc mới cho sự phát triển hạ tầng công nghiệp khí Việt Nam, dự án đã được PV GAS giao cho Khí Đông Nam quản lý vận hành, và với kinh nghiệm quản lý vận hành của mình, công ty đã và đang tổ chức, phối hợp với các bên liên quan vận hành an toàn liên tục hệ thống đường ống này.

Với bề dày kinh nghiệm 20 năm quản lý, vận hành các công trình khí, tuyến ống dẫn khí trên bờ, ngoài khơi, cộng với sự nhiệt huyết, năng động trẻ trung của các cán bộ công nhân viên vận hành dự án Hàm Rồng - Thái Bình, Khí Đông Nam đã hoàn toàn làm chủ trong việc tiếp nhận các dự án khí Hàm Rồng- Thái Bình, xứng đáng là đơn vị đi đầu trong công tác vận hành các công trình khí.