Fishing is the major human activity within the ‘semi-enclosed’ Arafura and Timor Seas (ATS). Since the early 2000’s, Australia's sparsely populated, remote northern shores have reported very high levels of foreign, fishing-related marine debris. Limited information is available about the temporal and spatial variation of this fishing debris or its origin. We examine trends in derelict fishing nets (and marine debris) at multiple sites in the Northern Territory and Gulf of Carpentaria and, explore its potential origin and relationship with fishing activity in the region. Further, we investigate temporal trends in domestic and foreign fishing activity (legal and illegal) in the ATS and also foreign fishing vessel sightings in the northern waters of the Australian Exclusive Economic Zone (AEEZ). Our results confirm that foreign fishing debris (nets, rope and gear) is the major source of marine debris (63%) on Australia's northern shores. Over the period 2003–2008, a total of 2305 derelict fishing nets were washed ashore; of these, 89% were identified of foreign origin (i.e. manufacture), compared to 11% attributed to Australian fishing vessels or fisheries. Industrial foreign and Indonesian-flagged fisheries – particularly, illegal, unreported and unregulated (IUU) trawling activity – and small-scale Indonesian IUU fisheries (primarily targeting shark) in the Arafura Sea are likely the major sources of these nets. Derelict nets comprised mostly trawl nets (71%) and gillnets/drift nets (12%); with 95% of all identified net sourced from the nations of Taiwan, Indonesia, Thailand and Korea. Our data also supports consistent under-reporting by these foreign trawl operators in the Indonesian Exclusive Economic Zone (IEEZ) of the ATS. The arrival and increase in derelict nets in northern Australia post-2000 coincided with sharp increases in both industrial foreign fishing (illegal, legal) and Indonesian small-scale fisheries within the IEEZ waters of the ATS. Including, over the period 2000–2007, a 2-fold increase in ‘non-motorised’ vessels, and a 5-fold increase in the number of motorised vessels, particularly in vessels less than 5GT. Further, this major increase in fishing activity in the IEEZ corresponded to a 3-fold increase in foreign fishing vessels (FFVs) (legal, illegal) sightings in northern Australian waters. Within the AEEZ, derelict net loads and sightings of illegal FFVs, both peaked and reached a maximum in 2005 (188 kg km−1yr; 6956 vessels) and then sharply reduced (>80%) following major border control, surveillance and security operations in the northern Australia in 2005–2006. However, post-2007, illegal FFV sightings inside the AEEZ have increased again. Significantly, derelict nets and small-scale IUU fishing activity in the AEEZ is linked to a broader pattern of poverty, overfishing and displacement of small scale fishers in coastal fisheries in the Arafura Sea (and South East Asia), due primarily to the expansion of industrial (illegal, legal) trawl fisheries. Strengthening of regional fisheries management (particularly under the RPOA-IUU) is urgently required to tackle IUU fishing, the key source of fishing debris in the ATS. While fisheries capacity reduction is a critical priority, it needs to be supported by a regional multi-sectoral response framed within the context of food security and rural economic development.