My Book 500 GB - No free space despite being free of files

Hoping someone can help… I deleted all of the files from 500 GB My Book and I’m still receiving that the volume doesn’t have enough room to back up my mac (138 GB). The message states that I have 138 MB free. Do I need to reformat? 

Thank you. 

Hello, follow the link below for the steps to format the my book and then try again.