במהלך שנת 2003 תוקן חוק משק הגז הטבעי באופן המאפשר מתן רישיון הולכת לחברה ממשלתית. בהמשך לתיקון החוק, ולאחר קבלת החלטה בנושא בקבינט הכלכלי-חברתי (החלטה חכ/22 מיום 16 ביולי 2003), הוקמה בתאריך 23 ביולי 2003 חברת נתיבי הגז הטבעי לישראל בע”מ (נתיבי גז או נתג”ז), אשר מקימה את מערכת ההולכה של הגז הטבעי בישראל. החברה בשליטת ממשלת ישראל (100%). המטרות של נתג”ז הם הקמת מערכת ההולכה של הגז הטבעי וחיבור צרכנים גדולים וכן התחברות לרשתות החלוקה של בעל רישיונות חלוקה. חיבור הצרכנים באמצעות מתקן למדידה ולהפחתת לחץ (PRMS) אותו מזמין הצרכן או בעל רישיון החלוקה לפי העניין. דמי החיבור בגין הקמת המתקן העשה בהתאם לכללים שקובעת מועצת רשות הגז הטבעי.. מרבית צרכני מערכת ההולכה הם יצרני וצרכני האנרגיה הגדולים במשק: תחנות הכוח של חברת החשמל ושל יצרני חשמל אחרים, מפעלי תעשייה גדולים כגון כי”ל, מנא”י, אגן, בתי זיקוק, מתקני התפלה ובעלי רישיונות החלוקה. מספרם הכולל של הצרכנים המחוברים ישירות אל מערכת ההולכה לא צפוי לעלות על 50 . בעל רישיון הולכה אינו עוסק בשיווק הגז. הבעלות על הגז הזורם במערכת ההולכה היא של צרכני שירותי ההולכה, כאשר המערכת מהווה תשתית בלבד. בשנת 2004 נתג”ז קיבלה רישיון ל-30 שנים להקמה ותפעול מערכת להולכת גז טבעי. החברה מספקת גז לכל צרכני הגז בלחץ גבוה (16-80 בר וכל הצינורת מספקות גז בלחץ של בין 70-80 בר) ולצרכני גז בלחץ נמוך שצורכים יותר מ-2000 מ”ק/שעה ופחות מ-0.012 מ”ק לשנה. סך ההשקעות במערכת ההולכה בחמש שנים בין 2003-2008 הסתכמו ב-1.7 מיליארד שקל. ביום 12 בספטמבר 2006, יזמה הממשלה תיקון לחוק משק הגז הטבעי, לפיו הבעלות על מערכת הולכת הגז הטבעי תהיה בידי המדינה, וכן, קביעת תעריף ההולכה תעשה על ידי מועצת רשות הגז.ב-2009 יש לחברה הכנסות של כ-250 מיליון שקל לשנה. בנובמבר 2009 חברת נתיבי הגז הטבעי לישראל ביקשה לקבל הצעות למתן שירותי תכנון מפורט להקמת מערכת להולכת גז טבעי מלחץ גבוה במקטע קו ירושלים ומקטע קו נילית, עם זכות קרירה להזמנת שירותי תכנון נוספים בהיקף מוגבל. ב-7 בדצמבר 2009 מפעלי כימיקלים לישראל, השיקו את המעבר לשימוש בגז טבעי בתחנת הכוח של החברה בסדום עם התחברות של המפעל למערכת ההולכה.צנרת הגז החדשה בדרום, נמתחת על פני כ-135 ק”מ (מקריית גת דרך רמת חובב ועד לסדום).

בינואר 2010 השלימה נתג”ז גיוס אג”ח פרטי לגופים מוסדיים של 213 מיליון שקל בריבית של 4.6%, שיועד כדי לממן את המשך הקמת מערכת הולכת הגז הטבעי. על פי הדו”ח הכספי לשנת 2008, נתג”ז הפסידה 1.6 מיליון שקל, לעומת רווח נקי של 468 אלף שקל ב־2007. ההון העצמי של החברה נאמד ב־447 מיליון שקל ב־2008, לעומת 362 מיליון שקל ב־2007.