What do you do when the Military had incorrect or no record of your service? I have been asked this multiple times.

The audit and forensics aspect of your OMPF is not to be taken lightly. So often one document can give the foundation, and support lay evidence in multi areas whether a promotions board, or veteran claim process. The correction aspect was covered well by Sgt Ted. Yet worse is the "missing" or "No Record" question that is a major concern shared each era of transition or branch service. In cases of these the National Archives Personal Records has certified independent auditors, who can access your files, create a inventory. Or you yourself can make appointment. :little things like post hospital records may only be archived at that post. Check out
https://www.army.mil/article/78319/ Also the Library of Congress web lists countless links to assist,

contact DFAS because they keep records of all you pay.

If you have a copy of your DD214, this is a source document and a record of your service time, an enlistment contract is another source. Awards also cover time and space.

There is a very useful and highly reputable principally VA qualified attorney group extremely helpful with horrendously complex claims apart from vet groups, all of which are good and of course free that we cannot extol too highly, try to ask for a member who's also a vet, though all their members are quite good. Look at https://vetadvocates.org, or NOVA, they're all highly scrupulous about charging only what VA conntingency fees are allowed by law, honest, just thought it might be of help, that's why we're trying to get the word out about them, my wife and I, promise, we wouldn't recommend them if they weren't well worth seeking help from, promise.

No record of service? I'm not sure how that would happen because they are pretty good about recording training events and service records. There is paperwork issued when you are assigned to a new duty station and then there are orders published to move you somewhere else. So if they did have incorrect or missing records you could just take them your copies of the orders or certificates and they will update your records. I'm sure you probably kept all documents related to assignments or training records like I did. When I retired I still had Leave and Earning Statements from when I first joined. After 21 years I had about 4 boxes full of paperwork that was marked KEEP.

find as much paperwork and stick with it ,

it all ways Best to keep a copy of all your records.. or les just keep looking for them and it hard to find some of them just keep searching !!!!!

Check with the GI Rights Hotline.

I sent away for mine from Marine records in Kansas city and they had it all wrong and said some of my docs weren't even in my SRB?! Quality of the people they have working there leaves a lot to be desired.

It's almost imposible to get military records corrected when you lieve the service for any reason. Personnel offices don't care and loop corresspondance until you tire of the matter. My son is going through this right now. I went through it too. Not fun or respectful at all.