They have feelings, like fear of a predator and hope of evading that predator. In humans feelings are connected to beliefs, feelings are partially caused by beliefs, and humans react to feeling based on beliefs about their causes. Are fear and hope connected to beliefs in animals? Do animals have beliefs?
To add to jobermark's answer, dolphins and orcas show advanced hunting methods which can't be explained unless they had distinct beliefs and conceptualizations. In particular, different populations of the same species of orca show different advanced hunting methods and teach them to their children (i.e. they are taught by learning, not transmitted genetically). This is considered evidence not just of orcas having beliefs, but of them having population specific cultures and customs.
I think the evidence that dogs mourn the death of other dogs is pretty clear. They can become obsessive about the slowly disappearing scent, follow trails left by those dogs, make arrangements to allow for their comfort, etc.
The two clearest examples I have encountered lately:
1) After one of a pair of Bassett hounds belonging to my extended family died, the other would not sleep in a room that did not have a bed for the missing dog. If we did not bring the extra bed, he would go back and get one and bring it, up two flights of stairs, if necessary. (Considering how short Bassett's legs are, carrying large floppy things up stairs made for humans is quite a difficult task for one.)
2) I have just lost one of my own Retrievers, and when I walk the remaining dog, the walks are interrupted by long, obsessive tracking of trails left by the now-absent dog. You can tell this is focussed on that specific dog because, if the searching dog is left to pursue them, these searches often lead back to our own yard, to a specific spot, presumably one where the dead dog urinated, despite the fact we are surrounded by neighbor dogs.
Also, when alive, the other dog ate first. Now the remaining dog will not eat brands of food that were served during that time. She waits for the nonexistent dog to eat first in exactly the same way she did when he was alive.
This seems to imply an expectation that the absent dog is going to return, or that he can be found. It is hard to frame this as anything other than a real ontological belief in the existence of the dog, which is maintained contrary to mere evidence.
Machines as simple as thermostats can be said to have beliefs, and having beliefs seems to be a characteristic of most machines capable of problem solving performance. However, the machines mankind has so far found it useful to construct rarely have beliefs about beliefs. -- John McCarthy
Agree or not, the famous computer scientist's position illustrates how slippery the proposition "X has beliefs" is when we attempt to grasp and hold it.