PSR B1259-63 is a 48 ms pulsar in a highly eccentric 3.4-year orbit around the young massive star LS 2883. During the periastron passage the system displays transient non-thermal unpulsed emission from radio to very high energy gamma rays. We observed PSR B1259-63 with the Australian Long Baseline Array (LBA) at 2.3 GHz to trace the milliarcsecond (mas) structure of the source at three different epochs during the 2007 periastron passage. We have discovered extended and variable radio structure. The peak of the radio emission is detected at distances between 23 and 46 AU from the system assuming a distance to the system of 2.3 kpc, and the total extent of the emission is 120 AU. This is the first observational evidence that non-accreting pulsars orbiting massive stars can produce variable extended radio emission at AU scales. We also present the new LBA campaign covering five different orbital phases during the 2010–2011 periastron passage. These observations will allow us to separate the pulsed radio component from the transient extended emission.