Why does background-color only work with overflow: hidden?

The problem is not overflow.

The problem is that your ul has no height. It gets the color but you can not see ...

See:

ul {
    list-style-type: none;
    margin: 0;
    padding: 0;
    height:40px;
    background-color: #333;
}

li {
    float: left;
}

li a {
    display: block;
    padding: 8px;
}

    <ul>
      <li><a href="#">Home</a></li>
      <li><a href="#">Noticias</a></li>
      <li><a href="#">Contato</a></li>
      <li><a href="#">Sobre</a></li>
    </ul>

> Overflow

This is just the scroll bar.

So I understand, when you put this feature, you gave a minimum height for ul ...

As the @DiegoSantos said just put a height already solves, but this does not explain why with Overflow works and without.

The explanation is that overflow changes the context of the element. Here you can read about it: link

Even the overflow technique is used to correct parent height problems when Sons have some float set and parent has no height.

Here is the Mozilla documentation that covers the subject: link

  

A block formatting context is created by at least one of the   following:

     

• floats (elements where float is not none)
  
• block elements where overflow has a value other than > visible
  

In your case, your <li> has float:left , if you just strip it or put display:inline-block the BG color will appear, <ul> will gain the height of your <a> that is display:block .

Now if you want to continue using float:left the effect that overflow:hidden does is that <ul> assume the height of the child that has display:block in case its <a> . So that with overflow:hidden in <ul> any value of height, line-height, or padding for example that you put in <a> will be reflected in the height of the parent <ul>

See the example for float :

div {
  background-color: #f00;
  width: 200px;
}
div > div {
  float: left;
  background-color: aqua;
  width: 100px;
  height: 100px;
}
.over {
  overflow: hidden;
}

<div class="over">
  <div>com overflow no pai</div>
</div>
<br>
<div>
  <div>sem overflow no pai</div>
</div>