After  the war in 1945, the remains  of many unidentifiable  POW's were found along the route of  the  infamous march  from Sandakan to Ranau  - (Ranau being more  than 257 kilometres  inland from Sandaken).  These  remains  and others  taken from scattered  graves throughout  Borneo were taken  to a  then  existing cemetery  in Sandakan  which  was  already   laden  with  a large number of  POW graves.  However  this  primary   burial ground was  in a  flat  sea coast  area  and  at  certain times  was  liable  to  heavy  flooding which  for obvious reason   made  it impractical  to  continue  using  it  as  a  cemetery.  Therefore  the  War Cemetery on the Island  of  Labuan  was  created and  all the deceased from the Sandakan  cemetery  were transferred.

The total number  of graves  on Labuan is  3,905.   2,700  graves are those of the  men  from  Sandakan of  which  nearly  half  are unnamed  -  it  was reported  that of the 2,400 men who left Sandakan only 260 arrived at Ranau and most of these succumbed later. Only six survived to the end of the war.

Approximately  another 500 graves  are  those of  men  from Kuching, which was another  large prisoner of war camp  in  Borneo. 

Of  the  total  number  of graves,  1,726 are completely  unidentifiable -  neither  by  nationality  nor  name.  The majority of unidentified graves  is  due  to the destruction of all records  of the camps  in Borneo  by  the  then  Japanese Commander  before his capture.  812  are known British graves with 81 being unknown.

Also at Labuan  is  a Memorial  consisting of  numerous columns  surrounding  a  square paved  area  which  is dedicated  to  the  officers  and  men  of  the Australian  Forces.