Rumor: I heard there was a terrible fire and ALL Veterans' records were destroyed, is this myth or fact?
Mostly myth. Read the true story of the 1973 fire.
Don't panic! All is not lost. The VA will assist you in recreating your military record to the best of their ability. There are other repositories of knowledge and documents. Any detail that you can remember may assist the VA with this task. Submit buddy statements detailing your memories; any detail, dates, fellow service member's names, dates, or missions can help. The VA will then scour combat log books, ships' logs, the records of other veterans, etc... all in an effort to create a picture of your service.
Also, please be aware that in some instances Veterans have received letters from the VA stating that their records were destroyed and it later turned out to be untrue. Sometimes, the Veterans records are more difficult to obtain from the National Archives in St Louis and in the interest of time, the VA sends out a request for records from the Veteran themselves, hoping that the Veteran has kept records they may be able to submit to the VA. If you do have copies of your records, it is always best to submit those documents in response to these letters. If you do not have copies, respond to these letters with any information you can remember that may help the VA in their search.