I connected an 1 TB Toshiba external HDD previously used on windows pc to my new MacBook Air and a message popped up for if I wanted to use this drive for time machine backup and since this is the first time i'm using mac I clicked "later". I think it got formatted so I tried some data recovery softwares but was unable to recover any data. I had lot of data on it which I would like to recover, is it possible?
To recover data from an external HDD formatted by Mac, you can use software TestDisk. Formatting is mainly performed when the HD gets corrupted due to software conflicts, bad sector etc. In Mac OS X, you can use ‘Disk Utility’ to perform the formatting process. Once formatting is completed, you can use advanced data recovery tool.
Seconding Douglas Gordon's answer, I've had a lot of success recovering data with TestDisk in the past.
However if you are less comfortable using a command line tool, I would recommend Data Rescue as well. You could start with the free option (which allows recovery of up to 2GB of data) to see whether it will actually work for you. They even list your specific situation ("accidentally reformatted hard drive") as one of their use cases.