Large Transport; Low Wing; 2 Turbojet Eng
Flight Crew Last 90 Days 183; Flight Crew Type 499
Distraction; Communication Breakdown; Confusion
ATC Issue All Types; Deviation / Discrepancy - Procedural Clearance; Deviation / Discrepancy - Procedural Published Material / Policy; Ground Incursion Runway
Air Traffic Control Issued New Clearance; Air Traffic Control Issued Advisory / Alert
Human Factors; Procedure
Flying from EWR. We were number one for takeoff from Runway 04L at EWR and holding short of the runway.  We heard tower make a radio call clearing an aircraft for takeoff; but the initial call sign was garbled.  We paused a moment; no one answered; so we transmitted; '[call sign] cleared for takeoff runway 4L.'   Tower did not respond or correct us; so we proceeded onto the runway.  Shortly thereafter; tower stated that we had not been cleared yet.  We replied to him that we had in fact read back that we were cleared for takeoff; but received no correction from him that we weren't.  He then stated that we must have been stepped on during that transmission.
We were sequenced behind a [jet] on 'D' taxiing to RWY 4L. The jet was cleared into position and then cleared for takeoff. We then received our clearance to line up and wait on RWY 4L. The FO read back the clearance; we verified the runway to each other; and we taxied into position. As we waited for our takeoff clearance; the controller asked us if we had been cleared into position. We replied that we had and that we had read back our clearance. He replied that our readback must have been stepped on. He then cleared us for takeoff. We departed; switched to departure control; and proceeded on our way. No further discussion with ATC ensued.
An air carrier aircraft holding short of EWR Runway 4L entered the runway following a garbled transmission which they misinterpreted was their takeoff clearance after ATC did not respond to their confirming takeoff clearance.