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. It is one of the three galactic binary systems clearly detected at TeV energies, together with LS 5039 and LS I +61 303. We observed PSR B1259-63 after the 2007 periastron passage with the Australian Long Baseline Array at 2.3 GHz to trace the milliarcsecond (mas) structure of the source at three different epochs. We have discovered extended and variable radio structure. The peak of the radio emission is detected outside the binary system near periastron, at projected distances of 10-20 mas (25-45 AU assuming a distance of 2.3 kpc). The total extent of the emission is ~50 mas (~120 AU). This is the first observational evidence that non-accreting pulsars orbiting massive stars can produce variable extended radio emission at AU scales. Similar structures are also seen in LS 5039 and LS I +61 303, in which the nature of the compact object is unknown. The discovery presented here for the young non-accreting pulsar PSR B1259-63 reinforces the link with these two sources and supports the presence of pulsars in these systems as well. A simple kinematical model considering only a spherical stellar wind can approximately trace the extended structures if the binary system orbit has a longitude of the ascending node of omega ~ -40 deg and a magnetization parameter of sigma~0.005.